public class Test {
    // 题目1：打家劫舍 III
    public int rob(TreeNode root) {
        int[] ret = dsf(root);
        return ret[0] > ret[1] ? ret[0] : ret[1];
    }
    public int[] dsf(TreeNode root){
        if(root == null){
            return new int[2];
        }
        int[] ret = new int[2];
        int[] left = dsf(root.left);
        int[]right = dsf(root.right);
        ret[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        ret[1] = left[0] + right[0] + root.val;
        return ret;
    }

    // 题目2：打家劫舍 Ⅳ
    // 给定一个数组，找到里面的多个子序列A（长度为k）
    // 子序列里元素两两不相邻，找到 所有max(A)里的最小值、
    public int minCapability(int[] nums, int k) {
        int left = 1;
        int right = 1;
        for(Integer x : nums){
            right = Math.max(right, x);
        }
        while(left < right){
            int mid = left + (right - left) / 2;
            if(calculate(nums, k, mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean calculate(int[]nums, int  k, int cap){
        int f0 = 0 , f1 = 0;
        for(Integer x : nums){
            if(x > cap){
                f0 = f1;
            }else{
                int temp = f1;
                f1 = Math.max(f1, f0 + 1);
                f0 = temp;
            }
        }
        return f1 >= k;
    }


    // 题目3：爱吃香蕉的珂珂
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;
        for(Integer x : piles){
            right = Math.max(right, x);
        }
        while(left < right){
            int mid = left + (right - left) / 2;
            if(calculate(piles, mid) > h){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
    public int calculate(int[]piles, int speed){
        int sum = 0;
        for(Integer x : piles){
            sum += (x + speed - 1) / speed;
        }
        return sum;
    }

    // 题目4： 修车的最少时间
    // 这个题目如果从车辆分配去想就很麻烦。
    public long repairCars(int[] ranks, int cars) {
        long left = 1;
        long right = 101;
        for(Integer x : ranks){
            right = Math.min(x, right);
        }
        right = right * cars * cars;
        while(left < right){
            long mid = (left + right) >> 1;
            if(calculate(ranks, mid) >= cars){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public long calculate(int[]ranks, long time){
        long nums = 0;
        for(Integer x : ranks){
            nums += (long)Math.sqrt(time/x  );
        }
        return nums;
    }
}
